/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 064. 神奇的字典
 * @author: WXY
 * @create: 2023-01-07 11:14
 * @Version 1.0
 **/
public class offer_twentyone2_MagicDictionary {
    private boolean dfs(String searchWord, Trie node, int pos, boolean modified) {
        if (pos == searchWord.length()) {
            return modified && node.isEnd;
        }
        int index = searchWord.charAt(pos) - 'a';
        if (node.child[index] != null) {
            if (dfs(searchWord, node.child[index], pos + 1, modified)) {
                return true;
            }
        }
        if (!modified) {
            for (int i = 0; i < 26; i++) {
                if (i != index && node.child[i] != null) {
                    if (dfs(searchWord, node, pos + 1, true)) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    class MagicDictionary1 {
        String[] words;

        /**
         * Initialize your data structure here.
         */
        public MagicDictionary1() {

        }

        public void buildDict(String[] dictionary) {
            words = dictionary;
        }

        public boolean search(String searchWord) {
            for (String s : words) {
                if (s.length() != searchWord.length()) {
                    continue;
                }
                int diff = 0;
                for (int i = 0; i < s.length(); i++) {
                    if (s.charAt(i) != searchWord.charAt(i)) {
                        diff++;
                        if (diff > 1) {
                            break;
                        }
                    }
                }
                if (diff == 1) return true;
            }
            return false;
        }
    }

    //看不懂，没有提交到LeetCode
    class Trie {
        Trie[] child;
        boolean isEnd;

        public Trie() {
            child = new Trie[26];
            isEnd = false;
        }
    }

    class MagicDictionary {
        Trie root;

        /**
         * Initialize your data structure here.
         */
        public MagicDictionary() {
            root = new Trie();
        }

        public void buildDict(String[] dictionary) {
            for (String str : dictionary) {
                Trie node = root;
                for (char ch : str.toCharArray()) {
                    int index = ch - 'a';
                    if (node.child[index] == null) {
                        node.child[index] = new Trie();
                    }
                    node = node.child[index];
                }
                node.isEnd = true;
            }
        }

        public boolean search(String searchWord) {
            return dfs(searchWord, root, 0, false);
        }
    }

}
